297. 二叉树的序列化与反序列化

Similar Question

leading to the advanced question

Solution Tips

方案一: 深度优先 - 先序遍历

序列化

var serialize = function (node, res = []) {
  if (node !== null) {
    res.push(node.val); //{1}
    serialize(node.left, res); //{2}
    serialize(node.right, res); //{3}
  } else {
    res.push(null);
  }
  // 序列化成字符串
  return res.toString();
};

字符串形式 null 被序列化成空位，更加节省空间

与层次遍历的区别在于叶节点的 null 也需要 push，用于标记树的结构

反序列化

const serialize = data.split(',')

null 被序列化为空 > ["2", "1", "", "", "4", "3", "", "", …]

JSON 则是 [1,2,null,null,3,4,null,null,5,null,null]

解析 JSON

var deserialize = function (data) {
  const serialize = JSON.parse(data);
  return recursion(serialize);
};
function recursion(arr) {
  if (arr[0] === null) return arr.shift();

  const root = new TreeNode(arr.shift());
  root.left = recursion(arr);
  root.right = recursion(arr);

  return root;
}

解析字符串

var deserialize = function (data) {
  const serialize = data.split(",");
  const rt = recursion(serialize);
  return rt;
  function recursion(arr) {
    if (arr[0] === "") {
      arr.shift();
      return null;
    }

    const root = new TreeNode(arr.shift());
    root.left = recursion(arr);
    root.right = recursion(arr);

    return root;
  }
};

方案二: 广度优先 - 层次遍历

var serialize = function(root) {
  if(root===null) return JSON.stringify([null])
  const queue = [root]
  const res = []
  while(queue.length>0){
    const node = queue.shift()
	
    if (node) {
	    res.push(node.val);
	    queue.push(node.left);
	    queue.push(node.right);
    }
    else {
	    res.push(null)
    }
  }
  // 序列化成JSON
  return JSON.stringify(res)
}

const deserialize = (data) => {
    const list = JSON.parse(data);

    if (list[0] === null) return null;

    // 获取首项，构建根节点
    const root = new TreeNode(list[0]);
    // 根节点推入队列
    const queue = [root];
    // 初始指向list第二项
    let i = 1;

    // 指针越界，即扫完了序列化字符串
    while (i < list.length) {
        // 考察出列的节点
        const node = queue.shift();

        // 它的左儿子的值
        const leftVal = list[i];
        // 它的右儿子的值
        const rightVal = list[i + 1];

        // 是真实节点
        if (leftVal !== null) {
            // 创建左儿子节点
            const leftNode = new TreeNode(leftVal);
            // 认父亲
            node.left = leftNode;
            // 自己也是父亲，入列
            queue.push(leftNode);
        }
        if (rightVal !== null) {
            const rightNode = new TreeNode(rightVal);
            node.right = rightNode;
            queue.push(rightNode);
        }

        i += 2; // 一次考察一对儿子，指针加2
    }

    return root;  // BFS结束，构建结束，返回根节点
};